
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * 第一遍
     * @param nums
     * @param target
     * @return
     */
//    public int[] searchRange(int[] nums, int target) {
//        return new int[] {left_bound(nums, target), right_bound(nums, target)};
//    }
//
//
//    // 寻找左边界
//    int left_bound(int [] nums, int target) {
//        int left = 0, right = nums.length - 1;
//        // 搜素区间为【Left, right】
//        while (left <= right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] == target) {
//                right = mid - 1;
//            } else if (nums[mid] < target){
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        if (left >= nums.length || nums[left] != target) {
//            return -1;
//        }
//        return left;
//    }
//
//    // 寻找右边界
//    int right_bound(int[] nums, int target) {
//        int left = 0, right = nums.length - 1;
//        // 搜素区间为【Left, right】
//        while (left <= right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] == target) {
//                left = mid + 1;
//            } else if (nums[mid] < target) {
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        if (right < 0 || nums[right] != target) {
//            return -1;
//        }
//        return right;
//    }


    /**
     * 第二遍 2/28
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        return new int[] {left_bound(nums, target), right_bound(nums, target)};
    }

    int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (right < 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
